`
https://leetcode.cn/problems/minimum-height-trees/
`

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findMinHeightTrees = function (n, edges) {
  if (n === 1) {
    // base case，只有一个节点 0 的话，无法形成边，所以直接返回节点 0
    return [0];
  }
  // 构造邻接表
  const graph = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) {
    graph[u].push(v)
    graph[v].push(u)
  }

  // 找到所有叶子节点，也即度为 1 的节点
  const q = []
  for (let i = 0; i < graph.length; i++) {
    if (graph[i].length === 1) {
      q.push(i)
    }
  }

  // BFS
  // 大于等于2是因为有可能遇到对称的情况
  // 此时会有两个节点构造出来的树的同样最小的
  let nodeCount = n
  while (nodeCount > 2) {
    const sz = q.length
    nodeCount -= sz
    for (let i = 0; i < sz; i++) {
      const cur = q.shift()

      // 不断删掉叶子节点，当产生新的叶子节点时加入队列 
      for (const neighbor of graph[cur]) {
        // 将被删除的叶子节点的邻接节点的度减 1
        graph[neighbor] = graph[neighbor].filter(n => n !== cur);
        // 如果删除后，相连节点的度为 1，说明它也变成了叶子节点
        if (graph[neighbor].length === 1) {
          q.push(neighbor);
        }
      }
    }
  }

  return q
};